
def kadane(arr):
    curr = arr[0]
    max_sum = arr[0]

    for i in range(1, len(arr)):
        curr = max(curr + arr[i], arr[i])
        max_sum = max(curr, sum)

    return max_sum